﻿//T6 计算布尔⼆叉树的值
//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (root->val < 2)
//            return root->val;
//        bool left = evaluateTree(root->left);
//        bool right = evaluateTree(root->right);
//        return root->val == 2 ? left | right : left & right;
//    }
//};

//T7 求根节点到叶节点数字之和
//class Solution {
//public:
//    int sumNumbers(TreeNode* root) {
//        return dfs(root, 0);
//    }
//
//    int dfs(TreeNode* root, int presum)
//    {
//        presum = presum * 10 + root->val;
//        if (root->left == nullptr && root->right == nullptr)
//            return presum;
//        int ret = 0;
//        if (root->left)
//            ret += dfs(root->left, presum);
//        if (root->right)
//            ret += dfs(root->right, presum);
//        return ret;
//    }
//};


//T8	⼆叉树剪枝
//class Solution {
//public:
//    TreeNode* pruneTree(TreeNode* root) {
//        if (root == nullptr)
//            return nullptr;
//        root->left = pruneTree(root->left);
//        root->right = pruneTree(root->right);
//
//        if (!root->left && !root->right && root->val == 0)
//        {
//            delete  root;
//            return nullptr;
//        }
//        return root;
//    }
//};


//T9 验证二叉搜索树
//class Solution {
//public:
//    long long prev = LLONG_MIN;
//    bool isValidBST(TreeNode* root) {
//        if (root == nullptr)
//            return true;
//        bool left = isValidBST(root->left);
// 
//        if (left == false)//剪枝判断
//            return false;
// 
//        if (root->val > prev)
//            prev = root->val;
//        else
//            return false;//剪枝判断
//			
//        bool right = isValidBST(root->right);
//        return left && right;
//    }
//};

//T10 二叉搜索树中第k小的元素
//class Solution {
//public:
//    int count = 0;
//    int ret = -1;
//    int kthSmallest(TreeNode* root, int k) {
//        count = k;
//        dfs(root);
//        return ret;
//    }
//
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr || count == 0)
//            return;
//        dfs(root->left);
//        count--;
//        if (count == 0)
//        {
//            ret = root->val;
//            return;
//        }
//        dfs(root->right);
//    }
//};

//T11 二叉树的所有路径
//class Solution {
//public:
//    vector<string> ret;
//    vector<string> binaryTreePaths(TreeNode* root) {
//        if (root == nullptr)
//            return ret;
//        string path;
//        dfs(root, path);
//        return ret;
//    }
//    void dfs(TreeNode* root, string path) {
//        path += to_string(root->val);
//        if (root->left == nullptr && root->right == nullptr) {
//            ret.push_back(path);
//            return;
//        }
//        path += "->";
//        if (root->left)
//            dfs(root->left, path);
//        if (root->right)
//            dfs(root->right, path);
//    }
//};